|
The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges.〔(About the so-called SPFA algorithm )〕 However, the worst-case complexity of SPFA is the same as that of Bellman–Ford, so for graphs with nonnegative edge weights Dijkstra's algorithm is preferred.〔(SPFA算法 )〕 The SPFA algorithm was published in 1994 by Fanding Duan. == Algorithm == Given a weighted directed graph ''G'' = (''V'', ''E'') and a source vertex ''s'', the SPFA algorithm finds the shortest path from ''s'' to each vertex ''v'' in the graph. The length of the shortest path from ''s'' to ''v'' is stored in d(''v'') for each vertex ''v''. The basic idea of SPFA is the same as Bellman–Ford algorithm in that each vertex is used as a candidate to relax its adjacent vertices. The improvement over the latter is that instead of trying all vertices blindly, SPFA maintains a queue of candidate vertices and adds a vertex to the queue only if that vertex is relaxed. This process repeats until no more vertex can be relaxed. Below is the pseudo-code of the algorithm.〔(SPFA算法 )〕 Here ''Q'' is a first-in, first-out queue of candidate vertices, and w(''u'', ''v'') is the edge weight of (''u'', ''v''). procedure Shortest-Path-Faster-Algorithm(''G'', ''s'') 1 for each vertex ''v'' ≠ ''s'' in ''V''(''G'') 2 d(''v'') := ∞ 3 d(''s'') := 0 4 offer ''s'' into ''Q'' 5 while ''Q'' is not empty 6 ''u'' := poll ''Q'' 7 for each edge (''u'', ''v'') in ''E''(''G'') 8 if d(''u'') + w(''u'', ''v'') < d(''v'') then 9 d(''v'') := d(''u'') + w(''u'', ''v'') 10 if ''v'' is not in ''Q'' then 11 offer ''v'' into ''Q'' The algorithm can also be applied to an undirected graph by replacing each undirected edge with two directed edge of opposite directions. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shortest Path Faster Algorithm」の詳細全文を読む スポンサード リンク
|